import java.util.ArrayList;
import java.util.List;

/**
* @description: 842. 将数组拆分成斐波那契序列
* @author hewei
* @date 2022/9/1 16:19
* @version 1.0
*/

public class SplitIntoFibonacci {

    public static void main(String[] args) {
        SplitIntoFibonacci splitIntoFibonacci = new SplitIntoFibonacci();
        System.out.println(splitIntoFibonacci.splitIntoFibonacci("123456579"));
    }

    String MOD = Integer.MAX_VALUE + "";
    public List<Integer> splitIntoFibonacci1(String num) {
        int n = num.length();
        List<Integer> ans = new ArrayList<>();
        for (int i = 1; i < n - 1; i++) {
            if (i != 1 && num.charAt(0) == '0') break;
            if ((i > 10) || i == 10 && num.substring(0, i).compareTo(MOD) > 0) break;
            int temp1 = Integer.parseInt(num.substring(0, i));
            for (int j = i; j < n - 1; j++) {
                if (j != i && num.charAt(i) == '0') break;
                if ((j - i + 1 > 10) || j + 1 - i == 10 && num.substring(i, j + 1).compareTo(MOD) > 0) break;
                int temp2 = Integer.parseInt(num.substring(i, j + 1));
                ans.add(temp1);
                if (process(ans, temp1, temp2, j, num)) return ans;
                ans.clear();
            }
        }
        return ans;
    }


    public boolean process(List<Integer> list, int temp1, int temp2, int i, String s) {
        list.add(temp2);
        if (i == s.length() - 1) return true;
        for (int j = i + 1; j < s.length(); j++) {
            if (j != i + 1 && s.charAt(i + 1) == '0') return false;
            if (j - i > 10 || (j - i == 10 && s.substring(i + 1, j + 1).compareTo(MOD) > 0)) return false;
            if (Integer.parseInt(s.substring(i + 1, j + 1)) == temp1 + temp2 && process(list, temp2, temp2 + temp1, j, s)) return true;
        }
        return false;
    }

    public List<Integer> splitIntoFibonacci(String num) {
        List<Integer> ans = new ArrayList<>();
        if (dfs(ans, 0, 0, 0, num)) return ans;
        return new ArrayList<>();
    }

    public boolean dfs(List<Integer> list, int sum, int last, int index, String s) {
        if (index == s.length()) return list.size() >= 3;
        long temp = 0;
        for (int i = index; i < s.length(); i++) {
            if (i != index && s.charAt(index) == '0') return false;
            temp = temp * 10 + s.charAt(i) - '0';
            if (temp > Integer.MAX_VALUE) return false;
            if (list.size() >= 2) {
                if (temp > sum) return false;
                else if (temp < sum) continue;
            }
            int a = (int) temp;
            list.add(a);
            if (dfs(list, last + a, a, i + 1, s)) return true;
            list.remove(list.size() - 1);
        }
        return false;
    }
}
